package com.arron.algorithm.leetcodetop100.动态规划;

import java.util.Arrays;

public class 无重叠区间_动态规划 {



    // 动态规划超时
    // 题意转换，最少删除区间--》 最多不重叠的区间
    public int eraseOverlapIntervals(int[][] intervals) {

        if (intervals.length == 1){
            return 0;
        }

        //按照区间左端点排序
        //,[1,100],[1,11],[2,12],[11,22]
        Arrays.sort(intervals, (a,b)->a[0]-b[0]);


        //定义dp dp[i] 表示 前i个最多的不重叠的区间
        int[] dp = new int[intervals.length];
        //base case 每个区间自己算一个不重叠区间
        Arrays.fill(dp,1);

        //状态转移方程为 ： dp[i] = 前dp[i-1]的最大的不重叠区间数+1
        for (int i = 1; i < intervals.length; i++) {

            for (int j = 0; j < i; j++) {

                if (intervals[j][1] <= intervals[i][0]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }


       return intervals.length - dp[dp.length-1];
    }

    public static void main(String[] args) {

        无重叠区间_动态规划 objk = new 无重叠区间_动态规划();

        int[][] arrays = {{1,2},{1,2},{1,2}};
        System.out.println(objk.eraseOverlapIntervals(arrays));

    }
    //[-73,-26],[-65,-11],[-63,2],[-62,-49],[-52,31],[-40,-26],[-31,49],[30,47],[58,95],[66,98],[82,97],[95,99]

}



